package io.adrainty.algorithm.leetcode.normal;

import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @link <a href="https://leetcode.cn/problems/evaluate-division/description/">...</a>
 * @author adrainty
 * @version v1.0.0
 * @since 2024/5/1 19:36
 */
public class Solution399 {

    // value -> index
    private final Map<String, Integer> varMap = new HashMap<>();

    private final Map<Integer, String> reverseMap = new HashMap<>();

    private int curIndex = 0;

    private double[][] graph;

    public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
        // 1. build graph;
        int n = values.length;
        for (List<String> equation : equations) {
            getIndexOfString(equation.get(0));
            getIndexOfString(equation.get(1));
        }
        this.graph = new double[curIndex][curIndex];
        for (int i = 0; i < n; i++) {
            List<String> equation = equations.get(i);
            double value = values[i];
            int member1 = getIndexOfString(equation.get(0));
            int member2 = getIndexOfString(equation.get(1));
            this.graph[member1][member2] = value;
            this.graph[member2][member1] = 1.0 / value;
        }

        // 2. calcute the result;
        double[] ans = new double[queries.size()];
        for (int i = 0; i < queries.size(); i++) {
            List<String> query = queries.get(i);
            String member1 = query.get(0);
            String member2 = query.get(1);
            if (!varMap.containsKey(member1) || !varMap.containsKey(member2)) {
                ans[i] = -1.0;      // no variable in equations
                continue;
            }
            ans[i] = dfs(member1, member2, 1, new boolean[curIndex][curIndex]);
        }
        return ans;
    }

    private int getIndexOfString(String s) {
        if (varMap.containsKey(s)) return varMap.get(s);
        varMap.put(s, curIndex);
        reverseMap.put(curIndex, s);
        return curIndex++;
    }

    private String getStringOfIndex(int index) {
        if (index >= curIndex) return "";
        return reverseMap.get(index);
    }

    private double dfs(String member1, String member2, double res, boolean[][] isVisited) {
        if (member1.equals(member2)) return res;   // find route from n1 to n2
        int n1 = getIndexOfString(member1);
        for(int i = 0; i < this.curIndex; i++) {
            // search route from n1 to n2
            if (graph[n1][i] != 0 && !isVisited[n1][i])  {
                isVisited[n1][i] = true;
                String newIndex = getStringOfIndex(i);
                double cur = dfs(newIndex, member2, res * graph[n1][i], isVisited);
                if (cur != -1) return cur;
                isVisited[n1][i] = false;
            }
        }
        return -1;
    }

}
